package priv.mill.graph.search;

/**
 * 深度优先算法
 * 深度优先算法适合形成决策树,在某种情形下的对应策略
 */
public class DfsApp {

    public static void main(String[] args) {
        Graph graph = new Graph();
//        添加若干顶点
        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
//添加若干边
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);

        System.out.println("Visits:");
//        深度优先搜索
        graph.mst();
        System.out.println();


    }
}

/**
 * 图
 */
class Graph {

    private static final int MAX_SIZE = 20;
    private final Stack stack;//棧容器
    private Vertex[] vertexList;//頂點集合
    private int[][] adjMat;//边的映射关系,无向图,映射关系是一个上三角矩阵或者说对称的对角线矩阵
    private int nVerts;//顶点数量

    public Graph() {
        vertexList = new Vertex[MAX_SIZE];
        adjMat = new int[MAX_SIZE][MAX_SIZE];
        stack = new Stack();

    }

    /**
     * @functional 添加顶点
     * @param label
     *
     */
    public void addVertex(char label) {
        vertexList[nVerts++] = new Vertex(label);
    }

    /**
     * 添加边，因为是对称矩阵，所以同时添加两个位置
     * @param start
     * @param end
     */
    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }

    /**
     * 最小生成树
     * 广度优先和深度优先的搜索路径都能组成最小生成树
     */
    public void mst() {
        vertexList[0].wasVisited = true;//设置为已访问
        stack.push(0);//加入栈中
        while (!stack.isEmpty()) {
            int currentVertex = stack.peek();
            int v = getAdjUnvisitedVertex(currentVertex);
            if (v == -1) {//没有找到子节点
                stack.pop();
            } else {//找到了
                vertexList[v].wasVisited = true;
                displayVertex(currentVertex);//对节点的操作
                displayVertex(v);
                System.out.println();
                stack.push(v);
            }
        }
        for (int row = 0; row < nVerts; row++) {//还原被访问状态
            vertexList[row].wasVisited = false;
        }
    }

    /**
     * 查找关联顶点
     * @param vertexId
     * @return 找到返回关联的顶点,没找到返回-1
     */
    private int getAdjUnvisitedVertex(int vertexId) {
        for (int col = 0; col < nVerts; col++) {
            if (adjMat[vertexId][col] == 1 && !vertexList[col].wasVisited) {
                return col;
            }
        }
        return -1;
    }

    private void displayVertex(int i) {
        System.out.print(vertexList[i].label);
    }
}

class Vertex {

    public char label;
    public boolean wasVisited;

    public Vertex(char label) {
        this.label = label;
    }
}
